#include "tools.cpp"

class Solution {
  public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        // don't think about elems repeated
        int popi = 0;
        for (auto n : pushed) {
            data.push(n);
            while (not data.empty() and data.top() == popped[popi]) {
                data.pop();
                ++popi;
            }
        }
        return data.empty();
    }

  private:
    std::stack<int> data;
};

int main() {
    std::vector<int> pushed{1, 2, 3, 4, 5};
    std::vector<int> poped{4, 5, 3, 2, 1};
    Solution s;
    print(s.validateStackSequences(pushed, poped));
}
